#include <bits/stdc++.h>
using namespace std;

/*
3442. 奇偶频次间的最大差值 I
已解答
简单
相关标签
premium lock icon
相关企业
提示
给你一个由小写英文字母组成的字符串 s 。

请你找出字符串中两个字符 a1 和 a2 的出现频次之间的 最大 差值 diff = a1 - a2，这两个字符需要满足：

a1 在字符串中出现 奇数次 。
a2 在字符串中出现 偶数次 。
返回 最大 差值。

 

示例 1：

输入：s = "aaaaabbc"

输出：3

解释：

字符 'a' 出现 奇数次 ，次数为 5 ；字符 'b' 出现 偶数次 ，次数为 2 。
最大差值为 5 - 2 = 3 。
示例 2：

输入：s = "abcabcab"

输出：1

解释：

字符 'a' 出现 奇数次 ，次数为 3 ；字符 'c' 出现 偶数次 ，次数为 2 。
最大差值为 3 - 2 = 1 。
 

提示：

3 <= s.length <= 100
s 仅由小写英文字母组成。
s 至少由一个出现奇数次的字符和一个出现偶数次的字符组成。
*/

// 法一
class Solution {
public:
    int maxDifference(string s) {
        vector<int> freq(26, 0);     // 统计字符出现次数
        for (char ch : s) {
            freq[ch - 'a']++;
        }
        // 最大奇数频次
        int maxOdd = 0;
        int minEven = INT_MAX;
        // 遍历
        for (int count : freq) {
            if (count == 0)     continue;       // 未出现的就跳过
            if (count % 2 == 1)     maxOdd = max(maxOdd, count);
            else    minEven = min(minEven, count);
        }
        // 至少有一个偶数和奇数
        return  maxOdd - minEven;   
    }
};

// 存储方式不同
// 法二
class Solution {
public:
    int maxDifference(string s) {
        int n=s.size();
        int zimu[26];
        memset(zimu,0,sizeof(zimu));
        for(int i=0;i<n;i++){
            zimu[s[i]-'a']++;
        }
        int ma=0,mi=INT_MAX;
        for(int i=0;i<26;i++){
            if(zimu[i]==0) continue;
            if(zimu[i]&1){
                ma=max(ma,zimu[i]);
            }
            else{
                mi=min(mi,zimu[i]);
            }
        }
        return ma-mi;
    }
};